\begin{frame}
\frametitle{Marker Automata}

\begin{define}[AMk, DMk, NMk, UMk~\cite{Ito1997},
NMA(k)~\cite{Morita2004},~\cite{Blum:1967:AT:1674645.1675318}]

A two-dimensional alternating k-marker automaton $(k~\in~\mathbb{N})$
is a 7-tuple $M~=~(Z,~\Sigma,~\delta,~z_0,~\{0,~1\},~U,~E)$, where

\begin{itemize}
	\item Z is a finite set of states, $\Sigma$ is a finite input alphabet
	\item $z_0 \in$ Z the initial state
	\item $\{0, 1\}$ is the presence and absence signs of markers
	\item $U, E \subseteq Q$ is a set of universal and accepting states
	\item $\delta: ((Z \times \{0, 1\}^k) \times ((\Sigma \cup
		\{\#\}) \times \{0, 1\}^k)) \rightarrow ((Z \times \{0, 1\}^k)
		\times ((\Sigma \cup \{\#\}) \times \{0, 1\}^k)) \times
		\Delta)$ is the control function, where $\# \not\in \Sigma$ and $\Delta~=~\{U,
		D, L, R, N\}$.
\end{itemize}

\end{define}

\end{frame}

\begin{frame}
\frametitle{Possible properties}

\begin{define}[~\cite{Blum:1967:AT:1674645.1675318}]
\begin{itemize}
  \item Marker automata can have a set of \textbf{labeled markers} $\{m_1, \ldots,
  m_k\}$ or \textbf{unlabeled markers} $\{*, \ldots, *\}$.
  \item These markers may be \textbf{stacked} on a single square or not.
  \item A marker can be \textbf{physical} or \textbf{abstract}.
  \item To get the physical marker transferred from one position to another,
  the automaton must actually go to the marker and move it to its new
  position.
  \item At any moment the automaton may place a abstract marker $m_i$ on the
  particular square of the tape it is scanning, and at that moment any other
  occurence of $m_i$ on its tape instantly disappears.
\end{itemize}
\end{define}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Language hierarchy}

\begin{thm}[Theorem 2.1~\cite{Blum:1967:AT:1674645.1675318}]
A MA(k) that can place at most one marker on any empty square are just
as powerful as a MA(k) that can stack any number of these markers on
an empty square.
\end{thm}

\begin{thm}[Theorem 2.2~\cite{Blum:1967:AT:1674645.1675318}]
A MA(k) with k abstract markers can be simulated by one with k physical
markers and vice versa.
\end{thm}

\begin{thm}[Theorem 2.3~\cite{Blum:1967:AT:1674645.1675318}]
A MA(k) with unlabeled markers can simulate one with labeled markers and
vice versa.
\end{thm}

\begin{thm}[Theorem 3~\cite{Blum:1967:AT:1674645.1675318}]
$\mathcal{L}(MA(k))\subset\mathcal{L}(MA(2k + 4))$, $k \geq 0$
\end{thm}

\begin{proof}
There is a certain property P such that a 2k + 4 marker automaton can decide
whether or not a tape has the property, but no k-marker automaton can make this
decision.
\end{proof}

\begin{thm}[Corollary 1~\cite{Blum:1967:AT:1674645.1675318}, Theorem
2.1~\cite{Ito1997}] 
$\mathcal{L}(XMA(0))\subset\mathcal{L}(XMA(1))$, $X\in\{$D, N, U, A\}\\
$\mathcal{L}(MA(1))\subset\mathcal{L}(MA(2))$
\end{thm}
Note that $XFA = XMA(0)$.

\begin{thm}[Theorem 3~\cite{Blum:1967:AT:1674645.1675318}]
Any DMA(k) can be converted to the DMA(k) that always halts for any input.
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Closure properties}

\begin{thm}[Theorem 2.1~\cite{Ito1997}]
$\mathcal{L}(DMA(1))\text{, }\mathcal{L}(NMA(1))\text{,
}\mathcal{L}(UMA(1))\text{ and }\mathcal{L}(AMA(1))$ are not closed under
catenations, closure, cyclic closure and projection. 
\end{thm}

\begin{thm}[~\cite{Ito1997}]
$\mathcal{L}(DMA(1))\text{, }\mathcal{L}(NMA(1))\text{,
}\mathcal{L}(UMA(1))\text{ and }\mathcal{L}(AMA(1))$ are closed under
intersection. $\mathcal{L}(DMA(1))\text{, }\mathcal{L}(NMA(1))\text{ and
}\mathcal{L}(AMA(1))$ are closed under union. Moreover is $\mathcal{L}(DMA(1))$
closed under complementation.
\end{thm}

\end{frame}